class Solution:
	# @param {string} s1
	# @param {string} s2
	# @param {string} s3
	# @return {boolean}
	def isInterleave(self, s1, s2, s3):
		if len(s3) != len(s1) + len(s2):
			return False
		dp = [False for c in xrange(len(s1)+1)]
		for i in xrange(len(s2)+1):
			for j in xrange(len(s1)+1):
				if i == j == 0:
					dp[j] = True
				elif i == 0:
					if dp[j-1] and s3[j-1] == s1[j-1]:
						dp[j] = True
				elif j == 0:
					if dp[0] and s3[i-1] == s2[i-1]:
						dp[0] = True
					else:
						dp[0] = False
				else:
					if (dp[j-1] and s1[j-1] == s3[i+j-1]) or (dp[j] and s2[i-1] == s3[i+j-1]):
						dp[j] = True
					else:
						dp[j] = False
			# print dp
		return dp[-1]

if __name__ == '__main__':
	so = Solution()
	s1 = 'a'
	s2 = ''
	s3 = 'a'
	print so.isInterleave(s1,s2,s3)